#include <iostream>
#include <queue>

using namespace std;

/*
You are given a 2D array like below:
    x o o o o x
    x x x o o x
    o o x o x o
    o o x o o o
A blob is defined as 1 or more adjacent (8 adjacent) Xs. Find the number of blobs in the most efficient manner.
Example: 2D array above has 2 blobs. 

*/
// will refine later

#define MAX 100  
#define USED 0x80  
      
struct point  
{  
    int x,y;  
};  
      
void push_in_queue(int x, int y, queue<struct point> *q, char mat[MAX][MAX], int nrow, int ncol)   
{  
    if(x < 0 || x >= nrow || y < 0 || y >= ncol)  
        return;  
    struct point pnt;  
    if (mat[x][y] == 'X' && !(USED & mat[x][y]))  
    {          
        mat[x][y] = USED | mat[x][y];  
        pnt.x = x;  
        pnt.y = y;  
        q->push(pnt);  
    }  
}  
      
int count_blob(char mat[MAX][MAX], int nrow, int ncol)  
{     
    queue<struct point> que;  
    int cnt = 0;  
    int x, y;  
    point pnt, tmp;  
    if (nrow == 0 && ncol == 0)  
        return 0;  
              
    for(x = 0; x < nrow; x++)  
    {  
        for(y = 0; y < ncol; y++)              
        {  
            if (USED & mat[x][y])  
                continue;  
                      
            if (mat[x][y] == 'X')  
            {  
                cnt += 1;  
                mat[x][y] = USED | mat[x][y];  
                pnt.x = x;  
                pnt.y = y;  
                que.push(pnt);  
      
                while( !que.empty() )  
                {  
                    tmp = que.front();  
                    que.pop();                      
                    push_in_queue(tmp.x - 1, tmp.y,     &que, mat, nrow, ncol);  
                    push_in_queue(tmp.x - 1, tmp.y - 1, &que, mat, nrow, ncol);  
                    push_in_queue(tmp.x - 1, tmp.y + 1, &que, mat, nrow, ncol);  
                    push_in_queue(tmp.x + 1, tmp.y,     &que, mat, nrow, ncol);  
                    push_in_queue(tmp.x + 1, tmp.y - 1, &que, mat, nrow, ncol);  
                    push_in_queue(tmp.x + 1, tmp.y + 1, &que, mat, nrow, ncol);  
                    push_in_queue(tmp.x,     tmp.y - 1, &que, mat, nrow, ncol);  
                    push_in_queue(tmp.x,     tmp.y + 1, &que, mat, nrow, ncol);                     
                }                   
            }                      
        }  
    }  
    return cnt;  
}  

int main()
{
	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}